package com.johann.classify;

import com.johann.test.SwapArray;

// 希尔排序 是 复杂的插入排序
/*
ShellSort举例：

9 0 3 7 1 2 8 6 5 4
gap=4
9 0 3 7  1 2 8 6  5 4
1        5        9
1 0      5 2      9 4
1 0 3    5 2 8    9 4
1 0 3 6  5 2 8 7  9 4
gap=2
1 0  3 6  5 2  8 7  9 4
1    3    5    8    9
1 0  3 2  5 4  8 6  9 7
gap=1
1 0 3 2 5 4 8 6 9 7
0 1 2 3 4 5 6 7 8 9
 */
public class ShellSort {
    public void shellSort(Integer [] arr){
        // 1、先完成一个简单的插入排序，即gap=1
        // 2、假设gap为4
        for(int gap = 4; gap>0; gap>>=1){
            //i代表即将插入的元素角标
            for (int i = gap; i < arr.length; i++) {
                // j代表 与i同一组的数组元素角标
                for (int j=i;j>gap-1&& arr[j-gap]>arr[j];j-=gap){
                    new SwapArray(arr,j,j-gap);
                }
            }
        }
    }
}
